

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W5 Nazewnictwo </title>

</head>

<body 
    
    >
    
    
    
<div id=d3ma style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Nazewnictwo</font></b><br>
  <hr size=2><br>
  <b style=COLOR:#3d85c6><font size=3>Wprowadzenie</font></b><br>
  <hr size=2><br>
  <div id=m6:i style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2362fftgtjfs_b.png" style=HEIGHT:342px;WIDTH:500px>
  </div>
  <br>
  Zasoby muszą być w systemie jednoznacznie identyfikowane. Identyfikatory niskiego poziomu (systemowe) są trudne do zapamiętania, niewygodne i zależne od aktualnie stosowanej technologii. Stąd potrzeba wprowadzenia <i>nazw</i> , które będą wygodniejsze w użyciu, i które ukryją przed użytkownikiem szczegóły organizacji wewnętrznej systemu rozproszonego. Odwołanie dwóch rozproszonych procesów do zasobu o tej samej nazwie umożliwia jego dzielenie. Rozbiór (tłumaczenie) nazwy zasobu pozwala na jego zlokalizowanie. Nazewnictwo – jako zadanie systemu operacyjnego – występują również w systemach scentralizowanych, ale systemy rozproszone wymagają specjalizowanej realizacji systemu nazewniczego. Realizacja ta jest sama w sobie rozproszona, co jest konieczne dla osiągnięcia wysokiej efektywności i skalowalności tej usługi.<br>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Główne problemy nazewnictwa</font></b><br>
  <hr size=2><br>
  <div id=gt_n style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2363hswppzfw_b.png" style=HEIGHT:343px;WIDTH:500px><br>
    <br>
    Nazwy powinny być przyjazne dla użytkownika, stąd ich konstrukcja staje się ważnym zagadnieniem projektowym, tym bardziej, że błędne założenia mogą np. ograniczyć skalowalność systemu.<br>
    <br>
    <p>
      System nazewnictwa musi być w stanie obsłużyć bardzo dużą (i ciągle wzrastającą) liczbę jednostek. Problem skalowalności może szczególnie dać znać o sobie w systemach, gdzie lokalizacja jednostki może ulegać zmianie. W konsekwencji nie można np. bezproblemowo powielać informacji o aktualnym adresie, gdyż może on się stać nieaktualny w krótkim czasie.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Trzeci istotny problem nazewnictwa dotyczy zarządzania przestrzenią nazw, a szczególnie nazwami, do których nie ma już odniesień. Nazwy takie powinny być wykrywane, a zasoby związane z tymi nazwami zwalniane. Zagadnienie to jest szczególnie istotne w systemach obiektowych.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Nazwy i adresy</font></b><br>
    <hr size=2><br>
    <div id=w183 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2364c48rpg45_b.png" style=HEIGHT:344px;WIDTH:500px>
    </div>
    <br>
    <p>
      Stosowanie nazw jest wygodne ponieważ uniezależnia nas od zmieniających się adresów. Przykładem może być posługiwanie się nazwą serwera FTP zamiast jego adresem IP. Zmiana lokalizacji serwera i rekonfiguracja systemu nazewniczego powodują, że serwer jest nadal dostępny pod tą samą nazwą, pomimo zmiany adresu IP (czyli punktu dostępu). Nazwy, które nie zawierają w sobie elementów adresów są określane jako nazwy <b>niezależne</b> <b>od</b> <b>położenia</b> (ang. <i>location</i> <i>independent</i> ).
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Identyfikatory</font></b><br>
    <hr size=2><br>
    <div id=jm5m style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2365c845gm4d_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
    </div>
    Identyfikatory jednoznacznie identyfikują jednostki i nie zmieniają się. Zwykłe nazwy nie są tak jednoznaczne. Aby upewnić się, że dwa odwołania dotyczą tego samego zasobu wystarczy porównać identyfikatory występujące w tych odwołaniach. Adresy również, pomimo, że są unikalne, nie spełniają warunków wymaganych dla identyfikatorów, ponieważ mogą być powtórnie użyte dla oznaczenia innej jednostki (np. adres IP może być przypisany innemu komputerowi).<br>
    <br>
    <p>
      Adresy i identyfikatory są najczęściej reprezentowane w postaci łańcuchów bitów, a więc postaci nieczytelnej dla człowieka. Przykładem może być adres IP (32 bity), adres w sieci Ethernet (48 bitów), czy adres komórki w pamięci (np. 64 bity).
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Przestrzenie nazw</font></b><br>
    <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd4 title=Sr-5-wyk-1.0-Slajd4> </a><br>
    <div id=xsaz style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2366cxrrdzgm_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Przestrzeń nazw można zobrazować za pomocą zaetykietowanego grafu skierowanego z dwoma rodzajami węzłów. Węzły-liście (ang. <i>leaf</i> <i>nodes</i> ) reprezentują poszczególne jednostki i nie wychodzą z nich żadne nowe krawędzie. Węzeł taki przechowuje informacje o danej jednostce: jej adres, stan. Na rysunku węzły-liście zostały zaznaczone jako kółka. Drugim rodzajem węzłów są węzły katalogowe (ang. <i>directory</i> <i>node</i> ), które mają zaetykietowane krawędzie przychodzące i wychodzące. Każdy węzeł katalogowy jest oddzielną jednostką w systemie rozproszonym i posiada swój identyfikator. Krawędzie wychodzące są zaetykietowane i wskazują na inne jednostki poprzez ich identyfikatory. Na rysunku węzły katalogowe zostały zaznaczone w kwadratach.
      <p>
        <br>
      </p>
      <p>
        Jeden z węzłów w przedstawionym grafie nie posiada krawędzi przychodzących (węzeł X1). Jest to tzw. korzeń (ang. <i>root</i> <i>node</i> ) grafu nazewniczego. Z reguły w systemach nazewniczych występuje tylko jeden korzeń.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Przedstawiony rysunek jest przykładem organizacji nazw dla systemu plików. Węzły-liście to pliki a węzły katalogowe to po prostu katalogi.
      </p>
      <br>
      <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd5 title=Sr-5-wyk-1.0-Slajd5> </a><br>
      <b style=COLOR:#3d85c6><font size=3>Nazwy globalne i lokalne</font></b><br>
      <hr size=2><br>
      <div id=h1jh style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2367c3zc2fcs_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        Każda ścieżka w grafie może być zapisana jako ciąg etykiet odpowiednich krawędzi wraz z etykietą węzła startowego. Taki ciąg nazywamy <i>nazwą</i> <i>ścieżki</i> . Jeżeli nazwa ścieżki rozpoczyna się od korzenia, to jest to <b>ścieżka</b> <b>bezwzględna</b> (globalna). Nazwy ścieżek nie rozpoczynające się od korzenia będą określane jako <b>nazwy</b> <b>względne</b> (względem węzła startowego) lub nazwy lokalne.<br>
        <br>
        <p>
          W systemach plików do zapisu nazw plików stosuje się notację korzystającą z ukośników do oddzielania nazw poszczególnych krawędzi w grafie. Zapis <i>/</i> <i>home/basia/skrypt</i> oznacza więc odwołanie do pliku <i>skrypt</i> znajdującego się w katalogu <i>basia</i> , który z kolei jest podkatalogiem katalogu <i>home</i> , a ten jest bezpośrednim podkatalogiem katalogu głównego (korzenia systemu plików). Zapis <i>„/”</i> oznacza tu korzeń. Warto zauważyć, że ten sam plik jest dostępny również pod inną nazwą bezwzględną: <i>/</i> <i>usr/bin/edytuj</i> . W tym przypadku graf jest grafem skierowanym acyklicznym. Niektóre usługi nazewnicze dopuszczają jednie ściśle hierarchiczną postać, w więc graf nazw jest tam drzewem (każda jednostka ma dokładnie jedną bezwzględną nazwę ścieżki).
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Tłumaczenie nazw</font></b><br>
        <hr size=2><br>
        <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd6 title=Sr-5-wyk-1.0-Slajd6> </a>
        <div id=bh81 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2368f27t637r_b.png" style=HEIGHT:343px;WIDTH:500px><br>
          <br>
          Przestrzeń nazw definiuje organizację danych w postaci drzewa (grafu). Najczęściej wykonywaną operacją na takim drzewie jest operacja wyszukiwania obiektów o określonych nazwach czyli tłumaczenie nazw (inne określenia: rozbiór nazw, rozwiązywanie, rozkładanie, odwzorowywanie). Proces ten najczęściej realizowany jest iteracyjnie, począwszy od korzenia. Przeszukiwane są kolejne tablice katalogowe w celu znalezienia węzła wskazywanego kolejnym członem bezwzględnej nazwy. Pewnym problemem jest jednak znalezienie punktu startowego do rozpoczęcia przeszukiwania struktury katalogowej, ponieważ niskopoziomowy identyfikator korzenia teoretycznie powinien być zapisany w tablicy katalogowej węzła nadrzędnego, a takiego nie ma. W zależności od usługi nazewniczej problem ten różnie się rozwiązuje. Np. w systemach plików jest ogólnie wiadomym gdzie znajduje się blok opisujący katalog główny. Jest to informacja zakodowana w podsystemie obsługi plików bądź zakodowana w inny sposób w systemie operacyjnym.<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Synonimy</font></b><br>
          <hr size=2><br>
          <div id=dv-g style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2369vdqd55gk_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Niektóre systemy nazewnicze dopuszczają istnienie synonimów, zwanych często aliasami (ang. <i>aliases</i> ). Mechanizm ten jest bardzo użyteczny, gdyż pozwala postrzegać tą samą przestrzeń danych zorganizowaną w różne hierarchie.
            <p>
              <br>
            </p>
            <p>
              Synonimy mogą być implementowane na dwa sposoby. Pierwszy polega na rejestrowaniu kilku równoważnych nazw, w dowolnych miejscach hierarchii nazw, odnoszących się do tych samych zasobów. Rozwiązanie takie jest stosowane np. w uniksowych systemach plików w formie dowiązań twardych (ang. <i>hard</i> <i>links</i> ). Drugi sposób reprezentacji synonimów polega na utworzeniu specjalnych węzłów-liści w grafie nazewniczym, które nie identyfikują docelowych jednostek, a jedynie zawierają docelowe nazwy, z których należy skorzystać w dalszej kolejności. Proces tłumaczenia nazw po napotkaniu na taki węzeł specjalny inicjuje kolejny proces tłumaczenia dla nazwy pobranej z węzła specjalnego. W uniksowych systemach plików rozwiązanie takie określane jest jako dowiązania symboliczne (ang. <i>symbolic</i> <i>links</i> ).
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Montowanie</font></b><br>
            <hr size=2><br>
          </div>
          <div id=ohw5 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2370cvmw2rdb_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Tłumaczenie nazw można wykorzystać do przezroczystego łączenia różnych przestrzeni nazw. Wystarczy, że w tym celu w wybranym węźle katalogowym pierwszej przestrzeni adresowej umieszczony zostanie identyfikator węzła katalogowego z drugiej przestrzeni nazw. Pierwszy węzeł będzie określany jako <b>punkt</b> <b>montażu</b> (ang. <i>mount</i> <i>point</i> ), a węzeł katalogowy docelowej przestrzeni nazw to <b>punkt</b> <b>montowany</b> (ang. <i>mounting</i> <i>point</i> ). Punkt montowany zazwyczaj jest korzeniem przestrzeni nazw. Podczas tłumaczenia nazwy, która odnosi się do innej przestrzeni nazw następuje przekazanie usłudze nazewniczej tej przestrzeni nazw odpowiedniej części nazwy i proces tłumaczenia jest kontynuowany. Ważne jest aby punkt montażu zawierał pełną informację identyfikującą montowany węzeł, a więc nie tylko lokalny identyfikator, ale także wskazanie na nową przestrzeń nazw.
            <p>
              <br>
            </p>
            <p>
              Montowanie wymaga odwzorowania kilku nazw identyfikujących zdalny zasób: protokół musi być skojarzony z odpowiednią implementacją, nazwa serwera musi być przetłumaczona na adres, i w końcu nazwa punktu montowanego na jego identyfikator. Wszystkie parametry identyfikujące zdalny zasób mogą być zakodowane np. w postaci URL. Np. <i>nfs</i> <i>://</i> <i>galio.cs.put.poznan.pl/usr/local</i> identyfikuje zdalny węzeł katalogowy <i>/</i> <i>usr/local</i> na serwerze <i>galio.cs.put.poznan.pl</i> dostępny za pośrednictwem protokołu NFS.
            </p>
            <br>
            <br>
          </div>
        </div>
      </div>
      <div id=fm43 style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2372d7wtvqcc_b.png" style=HEIGHT:341px;WIDTH:500px>
      </div>
      <br>
    </div>
    Rysunek pokazuje przykład montowania zdalnego węzła katalogowego z serwera S2 do węzła katalogowego na serwerze S1. Punkt montażu <i>/</i> <i>export/user</i> zawiera wskazanie na punkt montowany <i>/</i> <i>home/basia</i> z serwera S2, np. w postaci <i>nfs</i> <i>://</i> <i>galio.cs.put.poznan.pl/home/basia</i> . Po zamontowaniu przestrzeni nazw serwera S2 na serwerze S1 można np. posługiwać się nazwą <i>/</i> <i>export/user/skrypt</i> , która będzie powodować odwołanie do pliku <i>skrypt</i> z katalogu <i>/</i> <i>home/basia</i> na serwerze S2.<br>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Globalna usługa nazewnicza</font></b><br>
    <hr size=2><br>
    <div id=b:5m style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2373fpm7g62r_b.png" style=HEIGHT:340px;WIDTH:500px><br>
      <br>
      Inną metodą integracji kilku przestrzeni nazw jest utworzenie wirtualnego węzła katalogowego, nadrzędnego w stosunku do wszystkich węzłów-korzeni z poszczególnych przestrzeni nazw. Podejście to zastosowano np. w globalnych usługach nazewniczych GNS (ang. <i>Global</i> <i>Name</i> <i>Service</i> ) firmy DEC. Pewnym problemem tego podejścia jest konieczność zmiany wszystkich używanych dotąd nazw poprzez doklejenie odpowiedniego członu z przodu. Rozwiązaniem może być automatyczne doklejanie prefiksu zgodnego z identyfikatorem serwera do wszystkich nazw i późniejsze tłumaczenie tych prefiksów na pełną ścieżkę. Przykładowo nazwa <i>/</i> <i>jan/dane</i> , którą posługuje się użytkownik na serwerze S1 zostałaby rozszerzona do <i>S1</i> <i>:/</i> <i>jan/dane</i> , a następnie prefiks ten zostałby odwzorowany na nazwę <i>/</i> <i>home</i> dając ostatecznie <i>/</i> <i>home/jan/dane</i> . Niestety rozwiązanie to pociąga za sobą konieczność utrzymywania tablicy odwzorowań identyfikatorów serwerów na odpowiednie nazwy, co przy bardzo dużej liczbie serwerów może ograniczać efektywność tego podejścia.<br>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Realizacja przestrzeni nazw</font></b><br>
      <hr size=2><br>
      <div id=drjd style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2374dbxrn2ht_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        <p>
          Duże przestrzenie nazw są organizowane najczęściej hierarchicznie. Jeżeli mają obsługiwać również dużą liczbę użytkowników rozproszonych geograficznie, to automatycznie sama usługa nazewnicza również musi być realizowana z wykorzystaniem wielu serwerów. Strukturę dużej przestrzeni nazw można podzielić na trzy logiczne warstwy. Warstwa globalna jest tworzona przez węzły najwyższego poziomu (korzeń i bliskie mu węzły). Na tym poziomie konfiguracja jest raczej stabilna, a najważniejszym wymaganiem stawianym serwerom tej warstwy jest wysoka dostępność. Niżej ulokowana jest warstwa administracyjna, w której ulokowane są węzły reprezentujące poszczególne organizacje i ich oddziały. Na tym poziomie mogą się znaleźć również węzły reprezentujące poszczególnych użytkowników (pracowników). Najniższa warstwa – warstwa kierownicza – zawiera węzły, które są najbardziej podatne na zmiany, a więc węzły reprezentujące poszczególne komputery i zasoby przechowywane na tych komputerach. Warstwa ta jest o tyle szczególna, że jej zarządzaniem zajmują się również indywidualni użytkownicy, modyfikując wpisy za które są odpowiedzialni.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Przykład hierarchii systemu DNS</font></b><br>
        <hr size=2><br>
        <div id=yk3r style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2375d5cjp2gg_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Przestrzeń nazw systemu DNS (ang. <i>Domain</i> <i>Name</i> <i>Service</i> ) podzielona jest na <b>strefy</b> (ang. <i>zones</i> ). Każda strefa jest obsługiwana przez oddzielny serwer nazw. Wymaga się, aby każda strefa miała przynajmniej jeden serwer zapasowy, który jest repliką serwera podstawowego. Serwery obsługujące nazwy wyższych poziomów mają większą liczbę kopii dla zwiększenia ich dostępności, gdyż awaria takiego serwera mogłaby pociągać za sobą niemożliwość przetłumaczenia nazw pochodzących z dużej części przestrzeni nazw.<br>
          <br>
          <p>
            <b>Efektywność</b> dostępu do danych zapewnia się w dużej mierze poprzez stosowanie pamięci podręcznych we wszystkich serwerach nazw. Jest to szczególnie istotne w odniesieniu do serwerów obsługujących główne strefy lub strefy znajdujące się wysoko w hierarchii. Do serwerów takich potencjalnie kierowanych może być bardzo wiele zapytań ze względu na dużą liczbę podlegających im nazw. Ze względu jednak na dużą stabilność odwzorowań znajdujących się wysoko w hierarchii, dane te mogą być przez długi czas buforowane w innych serwerach niższego poziomu. W ten sposób redukowana jest liczba zapytań kierowanych do głównych serwerów.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Awarie serwerów nazw w warstwie kierowniczej są odczuwalne głównie przez użytkowników znajdujących się w danej jednostce organizacyjnej i ewentualnie ich klientów. W tym przypadku nacisk kładzie się raczej na efektywność pracy takiego serwera niż na jego dostępność, która jest gwarantowana przez lokalnego administratora. Efektywność należy tu jednak uzyskiwać głównie poprzez instalację oprogramowania na szybkim komputerze i zapewnienie dobrej łączności, gdyż intensywne stosowanie pamięci podręcznych w przypadku często zmieniających się danych może nie dać dobrych rezultatów.
          </p>
          <br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd13 title=Sr-5-wyk-1.0-Slajd13> </a><br>
          <b style=COLOR:#3d85c6><font size=3>Serwery nazw DNS</font></b><br>
          <hr size=2><br>
          <div id=aa9s style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2376fx6zrhdb_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Tabela przedstawia własności serwerów nazw pracujących w różnych warstwach przestrzeni nazw w systemie DNS. W warstwie globalnej intensywnie stosowane jest zwielokrotnianie i przechowywanie podręczne. Działanie to jest konieczne dla uzyskania wysokiej dostępności danych. Oczywiście generuje to problemy z utrzymaniem danych w stanie spójnym. Tym bardziej, że kopie danych rozrzucone są po całej sieci (głównie w postaci zawartości pamięci podręcznych). Modyfikacja takich danych zawsze rozciągnięta jest mocno w czasie, chociażby ze względu na opóźnienia komunikacyjne nieuniknione w sieci tej skali.<br>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Iteracyjne tłumaczenie nazw</font></b><br>
            <hr size=2><br>
            <div id=e2:l style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2377dsk4m2cz_b.png" style=HEIGHT:340px;WIDTH:500px>
            </div>
            <br>
            Rozproszenie przestrzeni nazw na wiele serwerów przekłada się bezpośrednio na sposób realizacji procesu tłumaczenia nazw, który musi angażować wiele serwerów. Tłumaczenie nazw w systemie DNS może być realizowane na dwa sposoby: <b>iteracyjnie</b> (ang. <i>iterative</i> <i>name</i> <i>resolution</i> ) lub <b>rekurencyjnie</b> (ang. <i>recursive</i> <i>name</i> <i>resolution</i> ). Poniższy opis metod odpytywania systemu DNS zakłada dla uproszczenia, że nie jest wykorzystywane zwielokrotnianie danych ani przechowywanie podręczne.<br>
            <br>
            <p>
              Tłumaczenie nazw realizowane jest przez oprogramowanie klienta zwane <b>analizatorem</b> <b>nazw</b> (ang. <i>name</i> <i>resolver</i> ). Tłumaczenie iteracyjne, przedstawione na slajdzie, kontrolowane jest w całym zakresie przez klienta. Rozpoczyna się ono od wysłania zapytania o nazwę do serwera domeny głównej. W tym przypadku realizowane jest tłumaczenie nazwy <i>galio.put.poznan.pl</i> . Serwer domeny głównej nie zna odpowiedzi na to pytanie i nie może dokonać pełnego przetłumaczenia tej nazwy na adres, ale wie jaki serwer jest odpowiedzialny za domenę <i>pl</i> , która występuje na końcu tłumaczonej nazwy. W odpowiedzi serwer domeny głównej wysyła adres serwera domeny <i>pl</i> (oznaczony jako #pl). Klient uzyskując tą informację, wysyła kolejne zapytanie tym razem do serwera domeny <i>pl</i> , próbując przetłumaczyć pozostałą część poszukiwanej nazwy, a więc <i>galio.put.poznan</i> . Serwer nazw domeny <i>pl</i> odpowiada wskazując na serwer nazw domeny <i>poznan.pl</i> . Ostatecznie pytanie trafia do serwera nazw domeny <i>put.poznan.pl</i> , gdzie przechowywane są dane o komputerach znajdujących się w tej domenie, a więc m.in. o komputerze <i>galio</i> . Klient uzyskuje w ten sposób adres odpowiadający nazwie <i>galio.put.poznan.pl</i> .<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Zakłada się, że klient zna adres serwera domeny głównej. W praktyce lista tych serwerów nie jest zbyt obszerna i jest aktualizowana stosunkowo rzadko, więc jej utrzymywanie nie jest problematyczne.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Rekurencyjne tłumaczenie nazw</font></b><br>
            <hr size=2><br>
            <div id=kd4v style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2378xxbqk7n3_b.png" style=HEIGHT:343px;WIDTH:500px>
            </div>
            <br>
          </div>
        </div>
        Rekurencyjne tłumaczenie nazw polega na zleceniu translacji nazwy pojedynczemu serwerowi. Serwer domeny głównej nie znając odpowiedzi na pytanie przekazuje je dalej, nie odsyłając odpowiedzi od razu klientowi. Zapytanie przekazywane jest do serwera, który powinien znać odpowiedź lub takiego, który będzie w stanie przeprowadzić dalszy proces tłumaczenia nazwy. W przedstawionym przykładzie serwer domeny głównej przekazuje zapytanie do serwera domeny <i>pl</i> , ten do serwera domeny <i>poznan.pl</i> , a ten w końcu do serwera domeny <i>put.poznan.pl</i> , gdzie następuje ostateczne przetłumaczenie nazwy na adres. Odpowiedź wraca tą samą drogą, ale w przeciwnym kierunku.
        <p>
          <br>
        </p>
        <p>
          Z punktu widzenia klienta, odpowiedź zawsze nadchodzi z serwera, który został odpytany, co jest wygodne, gdyż upraszcza oprogramowanie klienta. Wadą tego podejścia jest większe zaangażowanie poszczególnych serwerów w proces tłumaczenia nazw, co pociąga za sobą ich większe obciążenie. W praktyce więc serwery domeny głównej nie realizują zapytań rekurencyjnych. Inną zaletą odpytywania rekurencyjnego jest oszczędność komunikacji. Odpytywanie odległych (w sensie geograficznym) serwerów nazw w trybie iteracyjnym pociąga za sobą konieczność przesyłania komunikatów na duże odległości (przez wiele routerów). W trybie rekurencyjnym informacja przekazywana jest na mniejsze odległości.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Przesyłanie odpowiedzi wykorzystywane jest do wypełniania pamięci podręcznych poszczególnych serwerów. Przykładowo serwer domeny <i>pl</i> po wykonaniu powyższego zapytania uzyskuje informację o adresie serwera nazw dla domeny <i>put.poznan.pl</i> , którą to informację może wykorzystać w przyszłości dla zoptymalizowania następnego pytania o inny komputer z tej domeny. W ten sposób postępuje proces <i>uczenia</i> <i>się</i> serwerów, w którym dzięki przechowywaniu podręcznemu serwery są w stanie bezpośrednio odpowiedzieć na najczęściej zadawane pytania.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          W praktyce zapytania zgłaszane przez klientów nie są wysyłane bezpośrednio do serwera domeny głównej, ale do lokalnego serwera nazw, którego głównym zadaniem jest pośredniczenie w tłumaczeniu nazw. Serwer taki ma za zadanie odpytywanie innych serwerów w celu uzyskania odpowiedzi i następnie przechowuje podręcznie uzyskane wyniki. Ponieważ serwer taki znajduje się blisko klienta, dostęp do niego jest bardzo szybki. Po pewnym czasie serwer taki zna również odpowiedzi na dużą część pytań klientów lub przynajmniej zna serwery nazw głównych domen, co pozwoli w przyszłości szybko uzyskać właściwą odpowiedź. Z drugiej strony uruchomienie lokalnego serwera zwalnia analizator nazw klienta z konieczności przechowywania listy adresów serwerów nazw domeny głównej. Wystarczy w celu odwzorowania nazwy posłużyć się adresem lokalnego serwera nazw.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Rekordy zasobowe systemu DNS</font></b><br>
        <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd16 title=Sr-5-wyk-1.0-Slajd16> </a><br>
      </div>
      <div id=pu4- style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2379ptdn8gdp_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        Przestrzeń nazw w systemie DNS jest zorganizowana w postaci drzewa. Nazwy poszczególnych węzłów mają postać sekwencji etykiet rozdzielonych kropką, począwszy od etykiety najniższej w hierarchii a skończywszy na etykiecie najwyższej w hierarchii. Ponieważ hierarchia jest drzewem, to nazwy krawędzi tego drzewa wykorzystuje się do etykietowania samych węzłów. Korzeń jest oznaczany po prostu „.”, choć w zapisie nazw węzłów jest to z reguły pomijane. Nazwy nie rozróżniają małych i wielkich liter. Przykładowa nazwa <i>put.poznan.pl</i> <i>.</i> oznacza węzeł <i>put</i> będący podrzędnym węzłem w stosunku do węzła <i>poznan</i> , który z kolei jest podrzędny w stosunku do <i>pl</i> . Węzeł <i>pl</i> podlega bezpośrednio korzeniowi hierarchii.<br>
        <br>
        <p>
          Poddrzewa przestrzeni nazw w systemie DNS są nazywane <b>domenami</b> (ang. <i>domain</i> ). Nazwa ścieżki od korzenia całej przestrzeni nazw do korzenia domeny nazywamy <b>nazwą</b> <b>domeny</b> (ang. <i>domain</i> <i>name</i> ). Domena może obejmować kilka stref, np. domena <i>poznan.pl</i> może obejmować zarówno strefę <i>put.poznan.pl</i> jak i strefę <i>man.poznan.pl</i> .<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Konfiguracja domeny opisana jest zbiorem <b>rekordów</b> <b>zasobowych</b> (ang. <i>resource</i> <i>records</i> ). Tabelka przedstawia najczęściej wykorzystywane typy rekordów zasobowych. Rekord SOA (ang. <i>Start</i> <i>of</i> <i>Authority</i> ) zawiera podstawowe informacje opisujące strefę, m.in. adres poczty elektronicznej administratora systemu. Rekord A (adres), najczęściej stosowany, zawiera adres IP przypisany do konkretnej nazwy domenowej. Dla komputerów z kilkoma adresami IP definiuje się kilka rekordów A. Rekord MX (ang. <i>mail</i> <i>exchange</i> ) zawiera wskazanie na serwer obsługujący pocztę dla danej domeny. Dla strefy może być zdefiniowanych kilka rekordów MX, każdy kolejny wskazuje na zapasowe serwery pocztowe. Rekordy NS (ang. <i>name</i> <i>server</i> ) zawierają adres serwera nazw obsługującego daną strefę. Na podstawie rekordów NS serwery nazw wiedzą gdzie kierować zapytania w celu dalszego tłumaczenia nazwy, której dany serwer nie potrafi do końca przetłumaczyć.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Rekord CNAME (ang. <i>canonical</i> <i>name</i> – nazwa kanoniczna) pozwala na zdefiniowanie dodatkowych nazw dla komputerów. W rekordzie tym znajduje się wskazanie na <b>nazwę</b> <b>kanoniczną</b> komputera, czyli jego unikalną, podstawową nazwę. Mechanizm ten wykorzystuje się często do definiowania pomocniczych nazw <i>www</i> czy <i>ftp</i> w ramach domen, które reprezentują konkretne komputery z tych domen. Np. nazwa <i>www.put.poznan.pl</i> może być dodatkową nazwą dla komputera <i>libra.put.poznan.pl</i> , albo inaczej mówiąc <i>libra.put.poznan.pl</i> jest kanoniczną nazwą dla nazwy <i>www.put.poznan.pl</i>.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          System DNS utrzymuje również informacje o odwzorowaniach odwrotnych, a więc o tłumaczeniach adresów IP na nazwy. Do reprezentowania tej informacji służą rekordy PTR (ang. <i>pointer</i> – wskaźnik). Odwzorowania odwrotne przechowywane są w specjalnej domenie <i>in-addr.arpa</i> , gdzie poszczególne nazwy budowane są na podstawie adresów IP, poprzez odwrócenie kolejności poszczególnych bajtów składowych adresu. Np. adres 150.254.30.34 reprezentowany jest nazwą <i>34.30.254.150.in-addr.arpa</i> . W rekordzie PTR znajduje się nazwa kanoniczna przypisana do danego adresu IP.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Realizacja systemu DNS</font></b><br>
        <hr size=2><br>
        <div id=h3ov style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2380hg9vqhcz_b.png" style=HEIGHT:344px;WIDTH:500px><br>
          <br>
          System DNS realizuje zasadniczo zadania warstwy globalnej i administracyjnej. Warstwa kierownicza realizowana jest przez system plików lub przez inne usługi.<br>
          <br>
          <p>
            Każda strefa jest obsługiwana przez serwer nazw, który z reguły jest zwielokrotniany dla zwiększenia dostępności. Synchronizacja danych pomiędzy serwerem <b>pierwotnym</b> (ang. <i>primary</i> ) a <b>wtórnym</b> (ang. <i>secondary</i> ) odbywa się poprzez okresową weryfikację aktualności danych na podstawie numeru wersji pliku strefowego (tekstowej bazy danych zawierającej rekordy zasobowe strefy). Po stwierdzeniu aktualizacji serwer wtórny prosi o przesłanie aktualnej konfiguracji, co określane jest jako <b>przekazywanie</b> <b>strefy</b> (ang. <i>zone</i> <i>transfer</i>).<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W slajdzie przedstawiono przykładowe rekordy zasobowe jakie mogłyby się znaleźć w pliku strefowym dla strefy <i>put.poznan.pl</i> . Pierwszy rekord A definiuje nazwę <i>galio</i> w domenie <i>put.poznan.pl</i> , a więc nazwę <i>galio.put.poznan.pl</i> , której przypisany został adres 150.254.111.89. Rekord MX wskazuje na serwer pocztowy dla poddomeny <i>cs.put.poznan.pl</i> . Kolejny rekord (NS) definiuje serwer nazw dla poddomeny <i>cs</i>&nbsp;; będzie nim komputer <i>libra.cs.put.poznan.pl</i> . Ponieważ sama nazwa serwera nazw dla domeny podrzędnej nie jest wystarczająca dla skontaktowania się z tym serwerem, w pliku znajduje się również tzw. rekord łączący, zawierający adres komputera <i>libra</i> (rekord A). Dzięki tym dwóm ostatnim rekordom możliwe jest poprawne przekazanie pytań o nazwy z domeny <i>cs.put.poznan.pl</i> do odpowiedniego serwera nazw.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W oddzielnym pliku strefowym zapisywane są odwzorowania odwrotne (z domeny <i>in-addr.arpa</i> ). W pliku tym może się znaleźć rekord PTR tłumaczący adres IP na nazwę. Dla powyższego przykładu domena odwrotna będzie miała nazwę <i>111.254.150.in-addr.arpa</i> , a odpowiedni rekord PTR będzie miał postać:<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            89 IN PTR galio.put.poznan.pl.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Lokalizowanie jednostek ruchomych</font></b><br>
          <hr size=2>
        </div>
        <br>
        <div id=k.zn style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2381f4986hgm_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Tradycyjne systemy nazewnicze (takie jak np. system DNS) nie nadają się do zarządzania często zmieniającą się informacją. Sytuacja taka występuje w przypadku realizacji odwzorowań jednostek mobilnych, zmieniających swoje adresy. Założenie o stabilności odwzorowań pozwala w przypadku systemu DNS stosować na szeroką skalę zwielokrotnianie i przechowywanie podręczne, dlatego, że ryzyko niespójności danych jest minimalne.<br>
          <br>
          <p>
            Zmiana lokalizacji komputera może dotyczyć zmiany adresu przy niezmienionej nazwie. Ta zmiana może być zrealizowana lokalnie przez administratora poprzez modyfikację odpowiedniego rekordu zasobowego. Propagacja takiej zmiany będzie w tym przypadku szybka.
          </p>
          <p>
            Zmiana lokalizacji komputera wraz ze zmianą jego nazwy jest już większym problemem. Z reguły użytkownicy spodziewają się, że będą mogli korzystać ze starej nazwy bez zmian. Zakłada się więc, że nazwa będzie pełniła rolę identyfikatora, a więc niezmiennej, unikalnej nazwy. Nazwa w systemie DNS nie spełnia jednak tego wymagania – zmienia się wraz ze zmianą lokalizacji, a stara nazwa może być powtórnie wykorzystana.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Przeprowadzenie zmiany nazwy serwera z zachowaniem starej można zrealizować na dwa sposoby. Pierwszy polega na zapisaniu pod starą nazwą nowego adresu. Niestety kolejne zmiany lokalizacji będą wymagały dokonywania modyfikacji zapisów na zdalnym, być może nie kontrolowanym już, serwerze nazw. W efekcie dalsze zmiany będą zbyt wolno propagowane.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Drugie rozwiązanie polega na zmianie starego wpisu, tak aby była dowiązaniem symbolicznym do nowej nazwy. Efektem ubocznym tego rozwiązania jest wydłużenie czasu realizacji tłumaczenia nazwy, ponieważ tłumaczenie to będzie musiało teraz dotyczyć dwóch nazw (starej i nowej). Przy dalszym przemieszczaniu liczba kroków tłumaczenia może jeszcze wzrosnąć.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Nazewnictwo a lokalizacja</font></b><br>
          <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd19 title=Sr-5-wyk-1.0-Slajd19> </a><br>
          <div id=i_21 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2382ckbjssdh_b.png" style=HEIGHT:375px;WIDTH:500px><br>
            <br>
            Tradycyjne usługi nazewnicze dokonują odwzorowania nazwy bezpośrednio na adres. Każda zmiana adresu wymusza automatycznie konieczność zmiany odwzorowania nazwa-adres (rysunek po lewej). Lepszym rozwiązaniem jest wprowadzenie identyfikatorów jednostek (rysunek po prawej). Identyfikatory nigdy się nie zmieniają i nie mogą być użyte ponownie do identyfikacji innych jednostek. Identyfikatory nie muszą mieć postaci wygodnej do użycia dla człowieka; z reguły mają postać binarną.<br>
            <br>
            <p>
              Usługi nazewnicze zwracają identyfikator jednostki. Ponieważ identyfikator nigdy się nie zmienia można go lokalnie zapamiętać i dowolnie długo przechowywać. Nazwa danej jednostki może się w przyszłości zmienić, ale to nie wymaga ponownego odpytywania usługi nazewniczej, ponieważ znany jest już identyfikator poszukiwanej jednostki. Odwołanie się do jednostki wymaga jednaj jej zlokalizowania i jest to zadanie <b>usługi</b> <b>lokalizacji</b> (ang. <i>location</i> <i>service</i> ). Usługa lokalizacji dokonuje odwzorowania identyfikatora jednostki na adres (lub zbiór adresów).
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd20 title=Sr-5-wyk-1.0-Slajd20> </a><br>
            <b style=COLOR:#3d85c6><font size=3>Lokalizacja - proste rozwiązania</font></b><br>
            <hr size=2><br>
          </div>
          <div id=j5z4 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2383dmv4ckd8_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Lokalizację jednostek można przeprowadzić z wykorzystaniem <b>rozgłaszania</b> , o ile warstwa komunikacyjna umożliwia wykonywanie takiej operacji. Rozgłoszona wiadomość dociera do wszystkich jednostek, a odpowiada tylko ta, która spełnia określone w rozgłoszeniu warunki. Przykładem zastosowania tego podejścia jest protokół ARP (ang. <i>Address</i> <i>Resolution</i> <i>Protocol</i> ) mający na celu uzyskanie niskopoziomowego adresu komputera (adres z warstwy łącza danych) na podstawie jego adresu IP. Adres IP wysyłany jest w komunikacie rozgłoszeniowym i odpowiedź wysyłana jest tylko przez komputer, który faktycznie korzysta z tego adresu.<br>
            <br>
            <p>
              Rozgłaszanie staje się nieefektywne w przypadku dużych sieci, ponieważ angażuje wszystkie komputery i blokuje na pewien czas możliwość komunikacji wszystkich komputerów. Pewnym rozwiązaniem tego problemu jest zastosowanie częściowego rozgłaszania czyli <b>rozsyłania</b> (ang. <i>multicast</i> ). Rozesłanie wiadomości oznacza wysłanie jej do określonej grupy odbiorców. Istnieją protokoły w sieci Internet umożliwiające rozsyłanie wiadomości w skali całego globu. Mechanizm ten można wykorzystać do lokalizacji komputerów firmowych, które dołączając się do sieci uzyskują dynamicznie adresy IP. Każdy z komputerów po uzyskaniu dostępu do sieci może dołączyć się do odpowiedniej grupy rozgłoszeniowej, co umożliwi późniejsze wysłanie do tej grupy pytania lokalizacyjnego.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Mechanizm rozgłaszania/rozsyłania można wykorzystać również do lokalizacji najbliższej kopii danych. Odpowiedź na komunikat rozgłoszeniowy wysyłana będzie w tym przypadku przez wiele serwerów, ale istotna będzie kolejność odbioru tych wiadomości. Można założyć, że komputer który odpowie jako pierwszy jest najbliższy (lub najmniej obciążony).<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Innym prostym rozwiązaniem problemu lokalizacji są <b>wskaźniki</b> <b>naprowadzające</b> (ang. <i>forward</i> <i>pointers</i> ). Mechanizm ten polega na pozostawianiu w starej lokalizacji wskaźnika do nowej lokalizacji. Poszukiwanie jednostki sprowadza się wtedy do przejścia całego łańcucha wskaźników, aż dotrze się do właściwej jednostki. Rozwiązanie to jest bardzo proste koncepcyjnie i realizacyjnie, ale ma kilka wad. Łańcuch wskaźników może się bardzo wydłużyć, co spowoduje nieakceptowalne wydłużenie czasu oczekiwania na odpowiedź. Inna wada to konieczność przechowywania wskaźników w poszczególnych węzłach przez cały czas funkcjonowania systemu. W końcu rozwiązanie to może, w przypadku utraty któregoś ze wskaźników, doprowadzić do nieosiągalności jednostki.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Wskaźniki naprowadzające</font></b><br>
            <hr size=2><br>
            <div id=h:wt style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2384ct9nxsfc_b.png" style=HEIGHT:343px;WIDTH:500px><br>
              <br>
              Rysunek przedstawia działanie wskaźników naprowadzających. Żądanie klienta trafia (na podstawie informacji z usługi nazewniczej) do serwera S1, gdzie znajduje się wskaźnik zawierający adres serwera S2. Żądanie trafia do serwera S2, gdzie znajduje się wskaźnik do serwera S3. W serwerze S3 jest poszukiwany obiekt i zlecenie może zostać zrealizowane. Odpowiedź z serwera S3 może trafić bezpośrednio do serwera inicjującego przetwarzanie (S1) lub przejść tą samą drogę w odwrotnym kierunku po to, aby zaktualizować wskaźniki. W pierwszym podejściu odpowiedź trafi szybciej do klienta. W drugim kolejne żądanie kierowane do S1 po aktualizacji wskaźników będzie już mogło trafić bezpośrednio do serwera S3, bez względu na długość poprzedniej ścieżki. Działanie takie powoduje więc szybkie skracanie ścieżek przekierowań pomiędzy serwerami.<br>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Lokalizacja oparta na siedzibie</font></b><br>
              <hr size=2><br>
              <div id=rc4c style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2385fxg66qcs_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                Metoda lokalizacji oparta na wskaźnikach naprowadzających może doprowadzić do niedostępności zasobu jeżeli któryś ze wskaźników na ścieżce przestanie być dostępny. W takich sytuacjach można się wspierać (jako metodą awaryjną) wprowadzeniem <b>siedziby</b> (stanowiska macierzystego, ang. <i>home</i> <i>location</i> ) dla każdej jednostki. Jest to miejsce, pod którym zawsze można uzyskać informację o aktualnej lokalizacji jednostki.<br>
                <br>
                <p>
                  Rozwiązanie oparte na siedzibie zastosowano w systemie Mobile IP umożliwiającym komunikację z przemieszczającymi się komputerami. Dla każdego mobilnego komputera przewidziano program komunikacyjny (agent siedziby), dostępny zawsze pod tym samym adresem IP. Klient komunikuje się najpierw z agentem (1), próbując uzyskać aktualny adres serwera. Agent odpowiada (2) wysyłając adres serwera. Dalsza komunikacja (3-4) odbywa się już bezpośrednio pomiędzy klientem a serwerem. Wadą tego rozwiązania w przypadku stosowania w sieciach na szeroką skalę jest konieczność przeprowadzenia dodatkowej wymiany komunikatów z siedzibą, która może być zlokalizowana w zupełnie innym miejscu niż właściwy serwer.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Inną wadą metody opartej na siedzibie jest konieczność zapewnienia niezmiennej lokalizacji siedziby i ciągłości jej istnienia. Brak dostępu do siedziby pociąga bowiem za sobą brak dostępu do docelowego komputera. Trwała zmiana lokalizacji komputera nadal wymaga utrzymywania siedziby, być może w odległym miejscu. Pewnym rozwiązaniem jest tu zastosowanie tradycyjnej usługi nazewniczej do lokalizacji siedziby. Ponieważ lokalizacja siedziby rzadko ulega zmianie, klienci mogą sobie tą informację przechowywać podręcznie, nie tracąc na wydajności.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Podejście hierarchiczne</font></b><br>
                <hr size=2><br>
              </div>
              <div id=k4q0 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2386gtbjtfdv_b.png" style=HEIGHT:340px;WIDTH:500px><br>
                <br>
                Jednym z zastosowań mechanizmów lokalizacji jednostek jest telefonia mobilna (komórkowa). Podejście, które się tam stosuje polega na podejmowaniu próby lokalizacji jednostki z którą chcemy nawiązać łączność najpierw na podstawie lokalnego rejestru. Jeżeli to nie daje wyniku, nawiązywany jest kontakt z siedzibą jednostki w celu znalezienia jej aktualnego położenia. Schemat ten można uogólnić do wielopoziomowej hierarchii.<br>
                <br>
                <p>
                  Rysunek przedstawia przykładową hierarchię sieci lokalizacyjnej. Sieć podzielona jest na domeny. Domeny najniższego poziomu (domeny-liście) odpowiadają lokalnej sieci komputerowej lub komórce w telefonii mobilnej. Każda domena ma swój węzeł katalogowy, gdzie przechowywana jest informacja o wszystkich jednostkach znajdujących się w całej domenie. Węzeł katalogowy korzenia zawiera informacje o wszystkich jednostkach w systemie. Każda jednostka reprezentowana jest przez rekord położenia. Rekord położenia w domenie-liściu zawiera aktualny adres jednostki. Rekord położenia w węzłach wyższego poziomu zawiera wskaźnik do węzła niższego poziomu, gdzie dana jednostka faktycznie się znajduje. W ten sposób budowany jest łańcuch wskazań od korzenia do domeny-liścia, w której jednostka się znajduje.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Jednostki z wieloma adresami</font></b><br>
                <hr size=2><br>
              </div>
              <div id=zpsq style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2387fgspgwg9_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                <br>
                Jednostka może mieć wiele adresów. Informacja taka jest przechowywana w postaci wielu rekordów położenia znajdujących się w węźle katalogowym najmniejszej domeny zawierającej obie lokalizacje.<br>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Wyszukiwanie i wstawianie jednostki</font></b><br>
                <hr size=2><br>
                <div id=qs58 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2388c663j4d7_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Najczęściej wykonywaną operacją w systemach nazewniczych jest oczywiście tłumaczenie nazwy na adres. W przypadku lokalizacji hierarchicznej zapytanie wędruje po drzewie hierarchii domen. Na rysunku zapytanie klienta zostało zgłoszone w zaznaczonej domenie na dole po lewej stronie. Ponieważ węzeł ten nie zawiera rekordu położenia dla poszukiwanej jednostki, następuje przekazanie żądania do węzła nadrzędnego (1). Ten również nie posiada odpowiedniego rekordu i przekazuje żądanie do swojego węzła nadrzędnego (2). Węzeł ten posiada już odpowiedni rekord położenia, ale jest on jedynie wskaźnikiem do węzła podrzędnego, następuje więc przejście do tego węzła (3). Kolejny węzeł zawiera również wskaźnik (4). W końcu zapytanie trafia do węzła zawierającego rekord położenia z adresem (4). Odpowiedź odsyłana jest bezpośrednio do klienta.<br>
                  <br>
                  <p>
                    Poszukiwanie jednostek w modelu hierarchicznym wykorzystuje własność <b>lokalności</b> . Poszukiwanie obejmuje swoim zasięgiem coraz bardziej ogólne domeny, w skrajnym przypadku docierając do węzła katalogowego korzenia, który ma zarejestrowane wszystkie jednostki.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    <b>Wstawianie</b> informacji o nowej jednostce (rysunek po prawej) przebiega podobnie do operacji wyszukiwania. Załóżmy, że żądanie wstawienia pojawiło się w tej samej domenie-liściu, co w poprzednim przypadku. Żądanie takie jest przekazywane do węzłów nadrzędnych, aż dotrze do węzła, który posiada już odpowiedni rekord położenia (kroki 1 i 2). Jeżeli jest to rejestracja pierwszej kopii jednostki, to żądanie takie może trafić aż do korzenia. W węźle, który zna już rejestrowaną jednostkę (lub w korzeniu) następuje dodanie nowego rekordu ze wskaźnikiem do węzła podrzędnego zawierającego jednostkę. Następnie, żądanie przechodzi tą samą ścieżkę do miejsca, z którego wyszło, dodając po drodze wskaźniki tworzące ścieżką prowadzącą do domeny-liścia (kroki 3 i 4). W domenie-liściu następuje dodanie odpowiedniego rekordu położenia z adresem nowej jednostki.
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    <b>Usuwanie</b> jednostki z usługi lokalizacyjnej przebiega podobnie do operacji wstawiania. Po usunięciu rekordu położenia w domenie-liściu następuje przechodzenie wzwyż hierarchii i usuwanie odpowiednich wskaźników. Jeżeli w danym węźle po usunięciu wskaźnika rekord położenia staje się pusty, to jest on również usuwany. Może nie być pusty, jeżeli w węźle znajdowało się kilka wskaźników, wskazujących na alternatywne lokalizacje. W takim przypadku operacja usuwania kończy się. Jeżeli jednostka była jedyną w systemie, następuje usunięcie wszystkich wskaźników i rekordów położenia aż do korzenia.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Przechowywanie podręczne</font></b><br>
                  <hr size=2><br>
                  <div id=ctjs style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2389gprxztcr_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    Przechowywanie podręczne w przypadku usług nazewniczych dla jednostek mobilnych może być nieefektywne, ponieważ dane te ulegają częstym zmianom, co powoduje ostatecznie nie odnajdywanie poszukiwanych jednostek. Przechowywanie podręczne daje jest korzystne jedynie wtedy, gdy dane rzadko się zmieniają.<br>
                    <br>
                    <p>
                    W przypadku podejścia hierarchicznego może się okazać, że jednostka przemieszcza się, ale zawsze (czy prawie zawsze) w obrębie pojedynczej domeny. Jeżeli jest to domena-liść, to miejsce przechowywania adresu jednostki pozostaje cały czas to samo – jest to węzeł katalogowy tej domeny. Oznacza to, że ścieżka od korzenia do tego węzła jest stała i można ją przechować podręcznie. Zapytania o lokalizację tej jednostki mogą więc być kierowane bezpośrednio do węzła katalogowego, który zna odpowiedź. Jeżeli jednak przemieszczanie odbywa się na większym obszarze, to może następować zmiana przynależności do domen-liści. Nawet w tym jednak przypadku może istnieć domena wyższego poziomu, która obejmuje wszystkie odwiedzane przez jednostkę lokalizacje (i nie będzie to domena-korzeń). W takiej sytuacji można nadal stosować przechowywanie podręczne, ale dotyczące części ścieżki: od korzenia do domeny obejmującej wszystkie lokalizacje.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Na rysunku przedstawiono jednostkę, która znajduje się w domenie D2, ale przemieszcza się pomiędzy lokalizacjami w domenach D2 i D3. Domena D1 jest więc najmniejszą domeną obejmującą wszystkie możliwe lokalizacje jednostki. Adres węzła katalogowego D1 może więc być przechowywany podręcznie przez inne węzły w celu lokalizacji jednostki. Tak się dzieje w przypadku węzła katalogowego domeny D7. Dzięki przechowywaniu podręcznemu nie trzeba odwiedzać węzłów katalogowych domen D5 i D4 w celu lokalizacji wspomnianej jednostki.
                    </p>
                    <p>
                    Dodatkową optymalizacją możliwą do przeprowadzenia jest wymuszenie przechowywania docelowego adresu jednostki w węźle katalogowym domeny D1. Normalnie znajdowałby się tam jedynie wskaźnik do domeny D2 lub D3, w zależności od tego gdzie aktualnie znajduje się jednostka. Taka optymalizacja dodatkowo skraca czas pozyskania adresu.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Zastosowanie przechowywania podręcznego wskaźników może być pomocne, ale trzeba rozwiązać kilka problemów szczegółowych. Po pierwsze należy w jakiś sposób dokonać wyboru miejsca przechowywania adresu jednostki (w naszym przykładzie jest to węzeł katalogowy domeny D1). Po drugie należy dokonywać unieważniania wskaźników po rekonfiguracji danych w systemie nazewniczym. W powyższym przypadku rekonfiguracja byłaby potrzebna, gdyby powstała nowa kopia poszukiwanej jednostki np. w domenie D6. Zapytania zgłaszane w domenie D7 powinny wy tym przypadku być kierowane do nowej kopii, która jest najbliższa. Niestety nieaktualny wskaźnik przeniósłby poszukiwania do węzła domeny D1.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Usuwanie jednostek bez odniesień</font></b><br>
                    <hr size=2><br>
                  </div>
                  <div id=pwn8 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2390gw69g2c5_b.png" style=HEIGHT:344px;WIDTH:500px>
                  </div>
                  <br>
                  Usługi nazewnicze służą do lokalizacji jednostek. Jeżeli jednostka staje się niedostępna z powodu usunięcia wszystkich nazw odnoszących się do niej, powinna zostać usunięta. Jest to konieczne, aby zwolnić zasoby zajmowane przez tą jednostkę, zasoby które i tak nie są wykorzystywane. Działanie takie określa się mianem odśmiecania (ang. <i>garbage</i> <i>collection</i> ), a w przypadku systemów rozproszonych – <b>rozproszonym</b> <b>odśmiecaniem</b> . Działanie to jest szczególnie istotne w systemach rozproszonych obiektów, gdzie nie jest realizowane automatyczne usuwanie obiektów, które nie są już używane. Fakt nieużywania obiektu można stwierdzić poprzez wykrycie braku odwołań do niego. W systemach rozproszonych oznacza to, że nie ma w systemie żadnego pośrednika (czyli obiektu emulującego obiekt po stronie klienta). Trzeba również uwzględnić sytuację, gdy dwa obiekty wskazują na siebie wzajemnie, ale do których nie ma żadnych odwołań w systemie. W przypadku ogólnym do usunięcia kwalifikują się wszystkie obiekty, które nie są osiągalne ze <b>zbioru</b> <b>obiektów</b> <b>głównych</b> (ang. <i>root</i> <i>set</i> ). Można to zobrazować grafem powiązań pomiędzy obiektami, gdzie strzałka oznacza posiadanie odniesienia do obiektu wskazywanego.<br>
                  <br>
                  <p>
                    W systemie scentralizowanym wykrywanie i usuwanie obiektów bez odniesień jest proste. W przypadku systemów rozproszonych operacja taka wymaga komunikacji, która może być wolna lub zawodna, co ogranicza w konsekwencji wydajność i/lub skalowalność poszczególnych rozwiązań.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Zliczanie odniesień</font></b><br>
                  <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd28 title=Sr-5-wyk-1.0-Slajd28> </a><br>
                </div>
                <div id=jukw style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_23916c5kj7dj_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                  <br>
                  W systemach scentralizowanych weryfikację wykorzystania obiektów można przeprowadzić stosunkowo prosto poprzez utrzymywanie licznika odwołań do obiektu. Każde utworzenie takiego odwołania powoduje zwiększenie licznika, a usunięcie odwołania jego zmniejszenie. Osiągnięcie wartości zero przez ten licznik oznacza, że obiekt jest niedostępny i można go usunąć. W systemie rozproszonym realizacja tej koncepcji może być problematyczna np. z powodu zawodnej komunikacji. Utrata komunikatu potwierdzającego zwiększenie bądź zmniejszenie licznika odwołań spowoduje ponowne wysłanie tego samego zlecenia, powielając w ten sposób operację na liczniku. Odpowiedni protokół musi więc zająć się usuwaniem podwójnych komunikatów.<br>
                  <br>
                  <p>
                    Inny problem może wyniknąć z przekazywania odwołań pomiędzy procesami. Załóżmy, że proces P1 przekazuje do procesu P2 odwołanie do obiektu umieszczonego na serwerze S. Po wykonaniu tej operacji proces P1 nie potrzebuje już obiektu, więc wysyła do serwera żądanie zmniejszenia licznika odwołań. Jeżeli było to jedyne odwołanie w systemie, to może nastąpić w tym momencie usunięcie obiektu (licznik osiągnie wartość 0), dlatego że proces P2 nie zdążył jeszcze zarejestrować odwołania, które właśnie dostał od P1. Rozwiązaniem tego problemu może być wprowadzenie dodatkowego komunikatu wysyłanego przez proces P1 do serwera S <i>przed</i> przekazaniem odwołania do P2, informującego, że będzie przekazywane odwołanie. Dzięki temu obiekt nie zostanie usunięty nawet, jeżeli jego licznik odwołań osiągnie wartość zero.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Zaawansowane zliczanie odniesień</font></b><br>
                  <hr size=2><br>
                </div>
                <div id=mys4 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2392cht5qhf7_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Problemu wyścigu (ang. <i>race</i> <i>condition</i> ) występującego w zliczaniu odniesień można uniknąć poprzez wyeliminowanie komunikatów zwiększających licznik odwołań. Ważone zliczanie odniesień (ang. <i>weighted</i> <i>reference</i> <i>counting</i> ) polega na ustaleniu początkowej liczby całkowitej dla każdego obiektu i dzielenie jej przy każdym tworzeniu nowego odniesienia. Przykładowo: jeżeli przypisano obiektowi wagę 128, to po skopiowaniu odniesienia oryginał i kopia będą miały wagę równą 64. Jeżeli odniesienie-kopia utworzy kolejną kopię to będą one miały wagi równe 32. Usuwanie odniesień powoduje przesłanie informacji o znikającej wadze. Jeżeli waga osiągnie wartość 0, oznacza to, że wszystkie odniesienia zostały usunięte i obiekt może być też usunięty.<br>
                  <br>
                  <p>
                    Podstawową wadą tego podejścia jest ograniczona liczba kopii odniesień, które można utworzyć. Jeżeli waga osiąga wartość 1, to dalsze dzielenie nie będzie mogło być przeprowadzone. Rozwiązaniem jest wtedy wprowadzenie dodatkowego sztucznego odniesienia (wskaźnika naprowadzającego) do nowego obiektu-pośrednika, który będzie miał ustawioną wagę znów na dużą wartość. Usunięcie wszystkich odniesień do tego obiektu-pośrednika będzie powodować dopiero wysłanie komunikatu o usunięciu odniesienia do głównego obiektu. Podstawową wadą tej metody jest wydłużenie czasu dostępu przy długich łańcuchach wskaźników. Im dłuższy łańcuch tym większe jest również prawdopodobieństwo awarii.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Innym rozwiązaniem opartym na pośredniości jest <b>pokoleniowe</b> <b>zliczanie</b> <b>odniesień</b> (ang. <i>generation</i> <i>reference</i> <i>counting</i> ). Każde odniesienie jest opatrzone podwójnym licznikiem, gdzie pierwsza wartość oznacza liczbę kopii utworzonych na podstawie tego odniesienia, a druga oznacza generację odniesienia. Jeżeli na podstawie odniesienia P tworzona jest kopia Q, to licznik kopii w odniesieniu P jest zwiększany, a numer generacji kopii Q jest inicjowany na wartość o jeden większą od licznika generacji w P. Usuwając odniesienie wysyłane są obie wartości liczbowe. Serwer obiektu przechowuje tablicę G, w której pozycja i-ta oznacza liczbę kopii i-tej generacji. Usuwając odniesienie z parą (<i>i</i> , <i>k</i> ) zmniejszana jest o 1 wartość na pozycji <i>G[i</i> ] i jednocześnie zwiększana o k na pozycji <i>G[i+1</i> ]. Obiekt można usunąć gdy cała tablica G zostanie wyzerowana. Zaletą tego rozwiązania jest brak konieczności kontaktowania się z serwerem obiektu podczas tworzenia nowego odniesienia.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Wszystkie przedstawione tu rozwiązania zakładają niezawodną komunikację.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Spisywanie odniesień</font></b><br>
                  <hr size=2><br>
                </div>
                <div id=wcz2 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2393fzqdfscr_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Zamiast zliczania odniesień można stosować jawne spisywanie wszystkich odniesień. Spis taki (ang. <i>reference</i> <i>list</i> ) zachowuje własność <i>idempotentności</i> , która oznacza, że wielokrotne dodawanie czy usuwanie tych samych pozycji nie powoduje powstawania błędnych zapisów. W konsekwencji podejście to można zastosować w przypadku zawodnej komunikacji. Wymagane jest jedynie potwierdzenie wykonania operacji. Podejście to jest stosowane w Java RMI.<br>
                  <br>
                  <p>
                    Spisywanie odniesień jest wrażliwe na problem wyścigu, podobnie jak to miało miejsce w zliczaniu odniesień. Jeżeli proces <i>P1</i> przekazuje odniesienie do <i>P2</i> , to <i>P2</i> będzie rejestrował swoje nowe odniesienie na serwerze, a <i>P1</i> będzie wyrejestrowywał swoje. Jeżeli zgłoszenie procesu <i>P1</i> będzie pierwsze, to może się okazać, że lista odniesień stanie się na chwilę pusta, co możne spowodować usunięcie obiektu.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Podstawowa wada techniki spisywania odniesień polega na jej słabej skalowalności. Listy odniesień mogą się bowiem bardzo rozrastać. Aby to ograniczyć można stosować czasowe ograniczenie przechowywania informacji na liście, co jest określane jako <b>dzierżawa</b> (ang. <i>lease</i> ). Odniesienie, które nie odnowi swojej dzierżawy jest automatycznie usuwane z listy.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Identyfikowanie jednostek nieosiągalnych</font></b><br>
                  <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd31 title=Sr-5-wyk-1.0-Slajd31> </a><br>
                </div>
                <div id=pnkg style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2394htfmtcdh_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  W systemie rozproszonym może istnieć grupa obiektów, które wzajemnie na siebie wskazują, ale nie są osiągalne z zewnątrz. Takie obiekty również powinny zostać usunięte, ale metody przedstawione dotąd nie gwarantują ich usunięcia. Trzeba zastosować w tym przypadku <b>odśmiecanie</b> <b>ze</b> <b>śledzeniem</b> (ang. <i>tracing-based</i> <i>garbage</i> <i>collection</i> ). Metody te są kosztowne i słabo skalowalne ponieważ wymagają śledzenia wszystkich jednostek w systemie.<br>
                  <br>
                  <p>
                    W systemach scentralizowanych stosuje się kolektory typu <b>znakuj</b> <b>i</b> <b>zamiataj</b> (ang. <i>mark-and-sweep</i> ). Kolektor działa w dwóch fazach. W pierwszej fazie wychodząc od obiektów ze zbioru głównego przechodzi rekurencyjnie wszystkie odniesienia znacząc obiekty, które odwiedza na czarno. W drugiej fazie obiekty, które nie zostały oznaczone są usuwane. W podejściu trójkolorowym kolor szary wykorzystuje się do zaznaczenia obiektów, które zostały już osiągnięte, ale dla których nie sprawdzono jeszcze wszystkich odniesień. Odwiedzenie wszystkich odniesień obiektu powoduje zmianę koloru na czarny.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Rozproszone znakowanie i zamiatanie odbywa się w sposób zrównoleglony. Odwiedzone obiekty po przetworzeniu lokalnym kolektorem stają się szare do czasu sprawdzenia wszystkich odwołań do zdalnych obiektów. Sprawdzanie odwołań do zdalnych obiektów powoduje wysłanie komunikatu do zdalnego obiektu informującego o osiągalności. Po przetworzeniu wszystkich odniesień w obiekcie zdalnym odsyłane jest potwierdzenie. Przetworzenie wszystkich odniesień do obiektów zdalnych powoduje zmianę koloru na czarny.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Podstawową wadą znakowania i zamiatania jest konieczność całkowitego zablokowania przetwarzania na czas odśmiecania. W systemie rozproszonym oznacza to konieczność synchronizacji wszystkich rozproszonych procesów, co może być nieakceptowalne dla użytkowników. Rozwiązaniem może być zastosowanie odśmiecaczy przyrostowych. Niestety nie są one dobrze skalowalne. Działają one współbieżnie z aplikacjami, modyfikującymi graf osiągalności, co powoduje częste znakowanie obiektów kolorem szarym i komunikację między węzłami, która jednak nie prowadzi do efektywnego wykrywania nieosiągalnych obiektów.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Śledzenie w grupach</font></b><br>
                  <hr size=2><br>
                  <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-5-wyk-1.0-Slajd32 title=Sr-5-wyk-1.0-Slajd32> </a>
                  <div id=jjjt style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_23958jcfc9gt_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Mechanizm rozproszonego odśmiecania można zoptymalizować poprzez zorganizowanie przestrzeni obiektów w hierarchiczne grupy. Odśmiecanie jest wtedy realizowane najpierw lokalnie w każdym procesie, następnie w lokalnej grupie, a później w grupach wyższego poziomu. Do analizy odniesień wykorzystywane są liczniki odwołań; następuje porównanie liczby odniesień do obiektu z liczbą obiektów-pośredników odnoszących się do tego obiektu w danej grupie. W ten sposób można stwierdzić fakt istnienia odniesień spoza grupy, a więc odniesień, które będą musiały być przeanalizowane w kolejnym kroku. Lokalne odśmiecanie pozwala jednak wyeliminować z analizy sporą grupę obiektów, co pozwala na zredukowanie liczby węzłów w grafie analizowanym na wyższym poziomie. Jest to podstawowa przesłanka do stosowania hierarchicznych grup. W efekcie uzyskuje się wyższą skalowalność algorytmu – odśmiecanie realizowane jest bowiem na podobnej liczbie obiektów pomimo przechodzenia do wyższych grup w hierarchii.<br>
                    <br>
                  </div>
                  <br>
                </div>
              </div>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>